package LeetCode.Leet400_499.Leet490_499.Leet494;

/**
 * @ClassName Solution_2
 * @Author 孙天赐
 * @Date 2025/9/16 17:26
 * @Description TODO: 方法二   动态规划    8ms 29.85
 *                  背包容量为(target + sum) / 2，sum为数组元素和
 *                  找能装满该背包的方案个数，对于装满该背包的元素，前面加"+"，剩余元素加"-"，最终的和即为target
 *                  推导：
 *                      假设加法的总和为x，那么减法对应的总和就是sum - x。
 *                      所以我们要求的是 x - (sum - x) = target
 *                      即x = (target + sum) / 2
 *                      此时问题就转化为，用nums装满容量为x的背包，有几种方法。
 */
class Solution_2 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int len = nums.length;
        for(int i = 0;i < len;i++){
            sum += nums[i];
        }
        // 过滤掉无方案情况
        if(target > sum || target < -sum){
            return 0;
        }
        // 一个为奇数，一个为偶数，则也无方案
        if((target + sum) % 2 == 1){
            return 0;
        }
        int bagSize = (target + sum) / 2;
        // 用前len个元素装满背包容量为(target+sum) / 2 的背包有多少方案
        int[][] dp = new int[len][bagSize + 1];
        // 初始化第一行（只能装满容量为nums[0]的背包）
        for(int i = 0;i < bagSize + 1;i++){
            dp[0][i] = (nums[0] == i ? 1 : 0);
        }
        // 初始化第一列（背包容量为0，存在一种方案，什么都不放）
        // 如果有两个物品，物品0为0，物品1为0，装满背包容量为0的方法有4种
        // 三个就是8种
        int numZero = 0;
        for(int i = 0;i < nums.length;i++){
            // 统计0的个数
            if(nums[i] == 0){
                numZero++;
            }
            dp[i][0] = (int)Math.pow(2, numZero);
        }

        // 动态规划
        for(int i = 1;i < len;i++){
            for(int j = 1;j < bagSize + 1;j++){
                // 两种情况取和
                // 1.放物品i，则方案数为装满容量为(j - x)的背包的方案数)
                // 2.不放物品i，则方案书为装满容量为j的背包的方案数量
                // 注意考虑情况1，j - x小于0的情况
                if(j < nums[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = (dp[i - 1][j - nums[i]]) + (dp[i - 1][j]);
                }
            }
        }
        return dp[len - 1][bagSize];
    }

}
